package com.github.yangyishe.p200;

import com.github.yangyishe.TreeNode;

/**
 * 114. 二叉树展开为链表
 * https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 *
 * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [1,2,5,3,4,null,6]
 * 输出：[1,null,2,null,3,null,4,null,5,null,6]
 * 示例 2：
 *
 * 输入：root = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：root = [0]
 * 输出：[0]
 *
 *
 * 提示：
 *
 * 树中结点数在范围 [0, 2000] 内
 * -100 <= Node.val <= 100
 *
 *
 * 进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
 */
public class Problem114 {
    public static void main(String[] args) {
        Integer[] root=new Integer[]{1,2,5,3,4,null,6};
        TreeNode instance = TreeNode.getInstance(root);

        Problem114 problem114 = new Problem114();
        problem114.flatten(instance);

        TreeNode tmp=instance;
        while(tmp!=null){
            System.out.println(tmp);

            tmp=tmp.right;
        }
    }

    /**
     * 思路:
     * 逻辑没什么难点, 主要在于如何尽可能的减少空间利用, 即利用递归的回溯特性,返回值始终是想要的叶子结点
     * @param root
     */
    public void flatten(TreeNode root) {
        if(root==null){
            return;
        }
        nextTail(root);
    }

    public TreeNode nextTail(TreeNode node){
        if(node.left==null){
            return node.right==null?node: nextTail(node.right);
        }
        // assert node.left!=null
        if(node.right==null){
            node.right=node.left;
            node.left=null;
            return nextTail(node.right);
        }
        TreeNode tmp= nextTail(node.left);
        tmp.right=node.right;
        node.right=node.left;
        node.left=null;
        return nextTail(tmp.right);

    }
}
